package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列
 * https://leetcode-cn.com/problems/permutations/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/13 9:30
 */
public class Permute {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        backtracking(1, nums, new ArrayList<Integer>(), new int[nums.length], lists);
        return lists;
    }

    /**
     * 使用排列树作为搜索树
     * @param t
     * @param nums
     * @param list 存放当前解
     * @param strack 标记数字是否已在列表找
     * @param lists 存放解
     */
    private static void backtracking(int t, int nums[], List<Integer> list, int[] strack, List<List<Integer>> lists) {
        int len = nums.length;
        if (t > len) {
            lists.add(new ArrayList<>(list));
        } else {
            for (int i = 0; i < len; i++) {
                if (strack[i] == 0) {
                    list.add(nums[i]);
                    strack[i] = 1;
                    backtracking(++t, nums, list, strack, lists);//进入下一层
                    //回溯
                    --t;
                    list.remove(list.size() - 1);
                    strack[i] = 0;
                }
            }

        }
    }
}
